P5017 摆渡车

这道题我们先看一下数据范围:$n≤500,m≤100,0≤t_i≤4×10^6$

显然复杂度和$n,m$有关，既然如此，我们考虑用$t$的复杂度来解决此题吧。（此题解法不止一种）

我们用$dp[i]$表示在$i$时刻发车（不管是第几次），所有在$i$时刻之前到达的人的等待时间之和。$tot[i]$表示第$i$时刻有多少人开始等车，显然有：

$dp[i]=min(dp[j]+\sum_{k=j+1}^i tot[i]*(i-k))~~~(j ≤ i- m )$

我们再考虑一下边界条件，$Min_t$表示最先到的一个人来的时间，显然有$dp[Min_t]=0$。 $Max_t$表示最后一个人来的时间。最坏情况下，在最后一个人来的前一秒车开走了，那么总时间最多为$Max_t+m-1$。

最后，答案就是$min(dp[i])~~~(Max_t≤i≤Max_t+m-1)$(最后一个人开始等车)。

然后，我们就可以用$t^3$转移了。再看一下数据，得分$30$。

优化1

转移时的复杂度体现在求和，这个可以用前缀和优化。

我们用$tot[i]$表示前$i$时刻等车的人数之和（与前文定义不同），$sum[i]$表示前$i$时刻到达的人如果从0时刻开始等车，他们的时间之和。

那么，$tot[i]-tot[j]$就表示$i$到$j$这段时间里开始等车的人数之和，$sum[i]-sum[j]$表示第$j+1$时刻到第$i$时刻来到的人，从$0$时刻开始等车到他们来到的时间之和。$(tot[i]-tot[j])*i-(sum[i]-sum[j])$就是$j+1$到$i$时刻来到的人从开始等车到上车的时间之和，这就是我们转移时求的东西，处理前缀可以$\Theta(1)$转移。转移变为：

$dp[i]=min(dp[j]+(tot[i]-tot[j])*i-(sum[i]-sum[j]))~~~(j ≤ i- m )$

总复杂度$\Theta(t^2)$，得分50。

优化2

我们对优化1的式子继续拆分，并将只与i有关的部分拿出提出来，得到：

$dp[i]=min(dp[j]+tot[j]*i+sum[j]))+tot[i]*i-sum[i]~~~(j ≤ i- m )$

熟悉的同学可能会看出，这就是一道斜率优化的板题了。

转移只与$dp[j]+tot[j]*i+sum[j]$有关，我们考虑两个决策点$u,v$，且$u$优于$v$，即：

$dp[u]+tot[u]*i+sum[u]<dp[v]+tot[v]*i+sum[v]$

移项得：

$dp[u]-dp[v]+sum[u]-sum[v]<(sum[v]-sum[u])*i$

当$u<v$时，$sum[u]<sum[v]$。

$\frac{dp[u]-dp[v]+sum[u]-sum[v]}{sum[v]-sum[u]}<i$

当$u>v$时，$sum[u]>sum[v]$。

$\frac{dp[u]-dp[v]+sum[u]-sum[v]}{sum[v]-sum[u]}>i$

令$x_i=sum[i],y_i=dp[i]+sum[i]$，则原式变为：

$\frac{y_u-y_v}{x_u-x_v}<i$

或

$\frac{y_u-y_v}{x_u-x_v}>i$

我们就可以用单调队列维护斜率，可以证明，一定是一个下凸包（即单调递增），具体可以看一下网上斜率优化。

最后，转移$\Theta(1)$实现，总复杂度$\Theta(t)$,100分。

附上代码：

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int MAXN = 500;
const int MAXT = 4000000;
int n,m,x , Max_t;
int tot[ MAXT + 5 ] , sum[ MAXT + 5 ] , dp[ MAXT + 5 ];
int head = 1 , tail = 0;
int Queue[ MAXT + 5 ];

double delta_x( int u , int v ) {
	return tot[ v ] - tot[ u ] == 0 ? 1e-9 : tot[ v ] - tot[ u ];
}
double delta_y( int u , int v ) {
	return ( dp[ v ] + sum[ v ] ) - ( dp[ u ] + sum[ u ] );
}
double Slope( int u , int v ) {
	return delta_y( u , v ) / delta_x( u , v );
}

int main( ) {
	scanf("%d %d",&n,&m);
	for( int i = 1 ; i <= n ; i ++ ) {
		scanf("%d",&x);
		Max_t = max( Max_t , x );
		tot[ x ] ++ , sum[ x ] += x;
	}
	for( int i = 1 ; i <= Max_t + m - 1 ; i ++ ) {
		tot[ i ] += tot[ i - 1 ];
		sum[ i ] += sum[ i - 1 ];
	}
	
	for( int i = 0 ; i <= Max_t + m - 1 ; i ++ ) {
		if( i >= m ) {
			while( head < tail && Slope( Queue[ tail - 1 ] , Queue[ tail ] ) > Slope( Queue[ tail ] , i - m ) )
				tail --;
			Queue[ ++ tail ] = i - m;
		}
		while( head < tail && Slope( Queue[ head ] , Queue[ head + 1 ] ) <= i )
			head ++;
		dp[ i ] = tot[ i ] * i - sum[ i ];
		if( head <= tail ) dp[ i ] = min( dp[ i ] , dp[ Queue[ head ] ] + ( tot[ i ] - tot[ Queue[ head ] ] ) * i - sum[ i ] + sum[ Queue[ head ] ] );
	}
	int Ans = 0x3f3f3f3f;
	for( int i = Max_t ; i <= Max_t + m - 1 ; i ++ )
		Ans = min( Ans , dp[ i ] );
	printf("%d",Ans);
	return 0;
}